package algorithm

import (
	"log"
)

func PrintList(nums []int) {
	log.Println(nums)
}

func QuickSort(nums []int) {
	PrintList(nums)
	quickSortImpl(nums, 0, len(nums)-1)
	PrintList(nums)
}

//快读排序的关键是找到一个基准点,然后按照这个基准点把序列划分为2个
func quickSortImpl(nums []int, start int, end int) {
	if start == end {
		return
	}
	if len(nums) <= 1 {
		return
	}
	curValue := nums[start]
	curIdx := start
	for start < end {
		if curIdx < end {
			if nums[curIdx] > nums[end] {
				nums[curIdx] = nums[end]
				nums[end] = curValue
				start = curIdx + 1
				curIdx = end
			} else {
				end--
			}
		}
		if curIdx > start {
			if nums[curIdx] < nums[start] {
				nums[curIdx] = nums[start]
				nums[start] = curValue
				end = curIdx - 1
				curIdx = start
			} else {
				start++
			}
		}
	}
	if curIdx > 0 {
		beforeSlice := nums[:curIdx]
		quickSortImpl(beforeSlice, 0, len(beforeSlice)-1)
	}
	if curIdx+1 < len(nums) {
		afterSlice := nums[curIdx+1:]
		quickSortImpl(afterSlice, 0, len(afterSlice)-1)
	}
}
